Antara tahun 1831 hingga 1872 dianggarkan seramai 3,000 rekrut Afrika Barat,[3] yang sebahagiannya sukarela dan sebahagian lainnya kerahan, telah dibawa ke Jawa untuk berkhidmat dengan KNIL. Semasa Perang Jawa, Belanda telah kehilangan beribu-ribu anggota tentera Eropah[4] dan bilangan yang lebih besar lagi daripada tentera peribumi mereka. Kemerdekaan Belgium daripada Belanda pada tahun 1830 pula mengurangkan bilangan penduduk Belanda, jadi lebih sukar buat Belanda untuk menggantikan kerugian jiwa daripada sebelumnya. Sebaliknya, untuk memastikan kesetiaan tentera peribumi, mereka mahu bilangan askar peribumi dalam tentera terhad kepada kira-kira separuh daripada jumlah total kekuatan.[4] Mereka juga berharap tentera Afrika akan lebih tahan dengan iklim dan penyakit tropika di Hindia Timur Belanda berbanding dengan tentera Eropah.[4] Belanda mendapat inspirasi untuk merekrut tentera dari Afrika daripada rejimen-rejimen Hindia Barat British yang diwujudkan untuk mengawal pemberontakan hamba-hamba yang bekerja di Caribbean.[5] Pegawai-pegawai Belanda yang berada di Suriname dan Hindia Barat Belanda berkesempatan untuk menyaksikan tentera dari Hindia Barat British beraksi dan berpuas hati dengan kebolehan mereka. Penyelidik Belanda, Ineke van Kessel, menulis pihak Belanda juga terpengaruh dengan laporan positif Mejar Charles Hamilton Smith, seorang pegawai British tetapi dilahirkan di Antwerp sebagai Karel de Smet, yang juga kenalan peribadi kerabat diraja Belanda.[6] Justeru, pada tahun 1831 Gabenor J. Last di Elmina diarah untuk merekrut sebuah kompeni tentera seramai 150 orang Afrika untuk berkhidmat di Hindia Timur Belanda.

Dalam Bahasa Melayu mereka dipanggil "Orang Belanda Hitam" kerana memakai nama panggilan Belanda (Johannes, Mozes dan lain-lain) dan juga kerana berasa lebih unggul terhadap anggota tentera peribumi yang berasal dari pulau Jawa dan Ambon.[7] Ini disebabkan kenyataan bahawa mereka diserap ke dalam tentera penjajah sebagai orang Eropah.[4][nota 1] Alasan untuk kenyataan ini mungkin untuk mengelakkan semua kaitan kepada asal-usul perhambaan mereka. Mereka direkrut terutamanya di bekas tanah jajahan Belanda di Pantai Guinea, iaitu di St. George d'Elmina (di Ghana pada masa ini) oleh seorang wakil daripada Tentera Diraja Hindia Timur Belanda, namun sebahagiannya lagi dibeli di pasar hamba di Kumasi.[4] Sebahagian kecil pula berasal dari tempat yang lebih jauh lagi, iaitu dari kawasan yang pada masa ini ialah Burkina Faso, Mali, Niger, Ivory Coast, dan Benin.[8][9] Setelah tanah jajahan ini dipindahkan kepada British pada 6 April 1872 berikutan Perjanjian Sumatera 1871, kawasan depoh ini ditutup dan keterlibatan warga Afrika Barat dalam tentera Hindia Timur Belanda dihentikan secara beransur-ansur.[4]